package linked;

import java.util.HashSet;
import java.util.Set;
import java.util.Stack;

/**
 * 单向链表
 *
 * @author cooper
 * @date 2019-07-08
 */
public class SingleLinked {

    private SingleNode head;

    private SingleLinked() {
        head = new SingleNode(0);
    }

    /**
     * 创建一个新的链表
     */
    public static SingleLinked getNew() {
        return new SingleLinked();
    }

    /**
     * 添加元素到尾部
     */
    public void add(SingleNode node) {
        SingleNode last = getLast();
        last.next = node;
    }

    /**
     * 连接两个链表
     */
    public void append(SingleLinked linked) {
        SingleNode last = getLast();
        last.next = linked.head.next;
    }

    /**
     * 获取中间节点
     */
    public SingleNode getMiddle() {
        if (head.next == null) {
            return null;
        }
        SingleNode slow = head.next;
        SingleNode fast = head.next;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    /**
     * 获取链表最后一个元素
     */
    public SingleNode getLast() {
        SingleNode cur = head.next;
        if (cur == null) {
            return head;
        }
        while (cur.next != null) {
            cur = cur.next;
        }
        return cur;
    }

    /**
     * 打印链表
     */
    public void print() {
        SingleNode cur;
        if ((cur = head.next) == null) {
            return;
        }
        while (cur != null) {
            cur.print();
            cur = cur.next;
        }
        System.out.println();
    }

    /**
     * 打印环形链表
     */
    public void printCircle() {
        SingleNode cur;
        if ((cur = head.next) == null) {
            return;
        }
        Set<SingleNode> set = new HashSet<>();
        while (cur != null && !set.contains(cur)) {
            cur.print();
            set.add(cur);
            cur = cur.next;
        }
        cur.print();
    }

    /**
     * 利用栈 逆序打印
     */
    public void reversePrint() {
        if (head.next == null) {
            return;
        }

        Stack<SingleNode> stack = getStack();
        if (stack == null) return;
        while (!stack.empty()) {
            SingleNode node = stack.pop();
            System.out.println(node.toString());
        }
    }

    /**
     * 逆序打印
     */
    public void reversePrint2() {
        print(head.next);
    }

    private void print(SingleNode node) {
        if (node != null) {
            print(node.next);
            node.print();
        }
    }

    /**
     * 将链表压入栈，并返回栈
     */
    private Stack<SingleNode> getStack() {
        SingleNode cur;
        if ((cur = head.next) == null) {
            return null;
        }

        Stack<SingleNode> stack = new Stack<>();
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        return stack;
    }

    /**
     * 逆序 利用栈
     */
    public void reverseWithStack() {
        Stack<SingleNode> stack = getStack();
        if (stack == null) return;

        head.next = stack.pop();
        SingleNode cur = head.next;
        while (!stack.empty()) {
            cur.next = stack.pop();
            cur = cur.next;
        }
        cur.next = null;
    }

    /**
     * 非递归 反转
     */
    public void reverseNonRecursive() {
        SingleNode cur;
        if ((cur = head.next) == null) {
            return;
        }

        SingleNode pre = head, next;
        while (cur != null) {
            next = cur.next;
            if (cur != head.next) {
                cur.next = pre;
            } else {
                cur.next = null;
            }
            pre = cur;
            cur = next;
        }
        head.next = pre;
    }

    /**
     * 递归实现反转
     */
    public void reverseRecursive() {
        if (head.next == null) {
            return;
        }

        head.next = reverse(head.next);
    }

    private SingleNode reverse(SingleNode node) {

        if (node == null || node.next == null) {
            return node;
        }
        SingleNode n = reverse(node.next);
        node.next.next = node;
        node.next = null;
        return n;
    }

    /**
     * 获取链表长度
     */
    public int getLength() {
        SingleNode cur;
        int size = 0;
        if ((cur = head.next) == null) {
            return size;
        }
        while (cur != null) {
            size++;
            cur = cur.next;
        }
        return size;
    }

    /**
     * 倒数第K个节点
     */
    public SingleNode getBackwardsIndex(int k) {

        int size = getLength();
        if (size == 0 || k > size) {
            return null;
        }
        SingleNode node = head.next;
        for (int i = 0; i < size - k; i++) {
            node = node.next;
        }
        return node;
    }

    /**
     * 链表排序
     */
    public void sort() {

        if (head.next == null || head.next.next == null) {
            return;
        }
        SingleNode pre = head;
        SingleNode cur = head.next;

        while (cur != null) {
            if (cur.compareTo(pre) < 0) {
                //把cur删除，然后把cur放到合适位置
                pre.next = cur.next;

                //从head找到cur应该插入的位置
                SingleNode node1 = head, node2 = node1.next;
                while (cur.compareTo(node2) >= 0) {
                    node1 = node2;
                    node2 = node1.next;
                }
                node1.next = cur;
                cur.next = node2;
                cur = pre.next;
            } else {
                pre = cur;
                cur = cur.next;
            }
        }
    }

    /**
     * 删除重复节点
     * TODO
     */
    public void removeDuplicateNode() {

        SingleNode cur = head.next;
        if (cur == null) {
            return;
        }

        while (cur != null) {
            if (cur.compareTo(cur.next) == 0) {
                cur.next = cur.next.next;
            }
            cur = cur.next;
        }
    }

    /**
     * 判断两个链表是否相交
     */
    public boolean isCrossWith(SingleLinked linked) {

        SingleNode last1 = this.getLast();
        SingleNode last2 = linked.getLast();
        return last1 == last2;
    }

    /**
     * 获取第一个相交的节点
     */
    public SingleNode firstCressNode(SingleLinked linked) {

        if (!isCrossWith(linked)) {
            return null;
        }

        int len1 = getLength();
        int len2 = linked.getLength();
        SingleNode node1 = head.next, node2 = linked.head.next;
        // 长的先走|len1-len2|步，然后两个一起走，第一个相同的节点，就是所求
        int k = Math.abs(len1 - len2);
        if (len1 < len2) {
            while (k != 0) {
                k--;
                node2 = node2.next;
            }
        } else {
            while (k != 0) {
                k--;
                node1 = node1.next;
            }
        }
        while (node1 != null) {
            if (node1 == node2) {
                return node1;
            }
            node1 = node1.next;
            node2 = node2.next;
        }
        return null;
    }

    /**
     * 判断是否有环，如果有，则返回入环节点，如果没有返回null
     * 思路:
     * 1. 设计两个快慢指针，快指针一次走2步，慢指针一次走1步，如果快指针和慢指针能重合，则有环
     * 2. 有环的情况下，快指针从头节点开始，慢指针从所在节点开始，快指针一次走两步，慢指针一次走一步，相遇的节点为入环节点
     */
    public SingleNode isCircle() {
        if (head.next == null) {
            return null;
        }
        SingleNode fast = head.next, slow = head.next;
        boolean isCircle = false;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (fast == slow) {
                isCircle = true;
                break;
            }
        }
        if (isCircle) {
            fast = head.next;
            while (fast != slow) {
                fast = fast.next;
                slow = slow.next;
            }
            return fast;
        }
        return null;
    }

    /**
     * 是否是回文链表
     * 1. 使用栈，把链表所有元素放到栈里边，循环比较 栈的数据量 n
     * 2. 使用栈，找到中间节点，把链表后半部分节点放到栈中，循环比较 栈的数据量n/2
     * 3. 找到中间节点，把后半部分反转，遍历比较（比较完之后，将后半部分反转）
     */
    public boolean isHuiWen() {
        if (head.next == null) {
            return false;
        }

        Stack<SingleNode> stack = new Stack<>();
        SingleNode cur = head.next;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }

        cur = head.next;
        while (cur != null) {
            SingleNode pop = stack.pop();
            if (cur.compareTo(pop) != 0) {
                return false;
            }
            cur = cur.next;
        }
        return true;
    }

    /**
     * 使用栈，找到中间节点，把链表后半部分节点放到栈中，循环比较
     * 栈的数据量 n/2
     */
    public boolean isHuiWen2() {
        if (head.next == null) {
            return false;
        }
        SingleNode middle = getMiddle();
        int length = getLength();

        Stack<SingleNode> stack = new Stack<>();
        SingleNode cur = head.next;
        while (cur != null && cur != middle) {
            stack.push(cur);
            cur = cur.next;
        }
        if (length % 2 != 0) {//奇数
            stack.push(middle);
        }

        while (!stack.empty()) {
            SingleNode pop = stack.pop();
            if (pop.compareTo(middle) != 0) {
                return false;
            }
            middle = middle.next;
        }
        return true;
    }

    /**
     * 判断是否是回文结构
     */
    public boolean isHuiwen3(){
        //TODO

        // 找到中间节点，把后半部分反转，遍历比较（比较完之后，将后半部分反转）
        return false;
    }

    /**
     * 给定一个节点， 如何在节点值有序的环形链表中插入这个节点，并保证环形链表依然有序
     *
     * @param linked 节点值有序的环形链表
     * @param node   待插入的节点
     */
    public static void addOrdered(SingleLinked linked, SingleNode node) {

        if (linked.isCircle() == null) {//不是环形链表
            return;
        }

        SingleNode head = linked.head;
        if (head.next == null) {
            return;
        }

        SingleNode pre = head.next, cur = pre.next;

        while (cur != null && cur.compareTo(node) < 0) {
            pre = cur;
            cur = cur.next;
        }
        //找到要插入的位置， 在pre和cur之间
        pre.next = node;
        node.next = cur;

        //修改head指针的指向
        if (node.compareTo(head.next) <= 0) {
            head.next = node;
        }
    }

}
